{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# 基于用户的协同过滤算法\n",
    "<a id=\"orga55bd8d\"></a>\n",
    "\n",
    "## 基础算法\n",
    "\n",
    "在一个在线个性化推荐系统中，当一个用户A需要个性化推荐时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有听说过的物品推荐给A。这种方法称为基于用户的协同过滤算法。\n",
    "\n",
    "主要包括两个步骤。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org112bd2c\"></a>\n",
    "### 找到和目标用户兴趣相似的用户集合\n",
    "\n",
    "**利用行为的相似度计算兴趣的相似度。**\n",
    "\n",
    "给定用户 $u$ 和用户 $v$ ，令 $N(u)$ 表示用户 $u$ 曾经有过正反馈的物品集合，令 $N(v)$ 为用户 $v$ 曾经有过正反馈的物品集合。通过如下的Jaccard公式<sup><a id=\"fnr.1\" class=\"footref\" href=\"#fn.1\">1</a></sup>简单地计算 $u$ 和 $v$ 的兴趣相似度：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{uv} = \\frac{| N (u) \\cap N (v) |}{| N (u) \\cup N (v) | } \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "或者通过余弦相似度<sup><a id=\"fnr.2\" class=\"footref\" href=\"#fn.2\">2</a></sup>计算<sup><a id=\"fnr.3\" class=\"footref\" href=\"#fn.3\">3</a></sup>：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{uv} = \\frac{| N (u) \\cap N (v) |}{\\sqrt{| N (u) | | N (v) | }} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "比如以下面的用户行为记录为例，举例说明 **UserCF** 计算用户兴趣相似度的例子。\n",
    "\n",
    "用户行为记录举例：\n",
    "\n",
    "    A -> [a] [b] [d]\n",
    "    B -> [a] [c]\n",
    "    C -> [b] [e]\n",
    "    D -> [c] [d] [e]\n",
    "\n",
    "用户 $A$ 对物品 ${a, b, d}$ 有过行为，用户 $B$ 对物品 ${a, c}$ 有过行为，利用余弦相似度公式计算用户 $A$ 和用户 $B$ 的兴趣相似度为：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{AB} = \\frac{| \\{a, b, d\\} \\cap \\{a, c\\} |}{\\sqrt{| \\{a, b, d\\} | | \\{a, c\\} |}} = \\frac{1}{\\sqrt{6}} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "同理可以计算出用户 $A$ 和用户 $C$ 、 $D$ 的相似度：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{AC} = \\frac{| \\{a, b, d\\} \\cap \\{b, e\\} |}{\\sqrt{| \\{a, b, d\\} | | \\{b, e\\} |}} = \\frac{1}{\\sqrt{6}} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "w_{AD} = \\frac{| \\{a, b, d\\} \\cap \\{c, d, e\\} |}{\\sqrt{| \\{a, b, d\\} | | \\{c, d, e\\} |}} = \\frac{1}{3} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "实现余弦相似度的伪代码：\n",
    "\n",
    "```python\n",
    "def user_similarity(train):\n",
    "    import math\n",
    "\n",
    "    W = dict()\n",
    "    for u in train.keys():\n",
    "        for v in train.keys():\n",
    "            if u == v:\n",
    "                continue\n",
    "            W[u][v] = len(train[u].keys() & train[v].keys())\n",
    "            W[u][v] = W[u][v] / math.sqrt(len(train[u].keys()) * len(train[v].keys()))\n",
    "    return W\n",
    "```\n",
    "\n",
    "上述代码对两两用户都利用余弦相似度计算相似度。方法的时间复杂度是 $O(|U|\\times|U|)$ ，在用户数很大时非常耗时。\n",
    "\n",
    "**事实上，很多用户相互之间并没有对同样的物品产生过行为** ，即很多时候 $|N(u) \\cap N(v)|=0$ 。\n",
    "\n",
    "可以先计算出 $|N(u) \\cap N(v)| \\neq 0$ 的用户对 $(u,v)$ ，再对这种情况除以分母 $\\sqrt{|N(u)||N(v)|}$ 。\n",
    "\n",
    "建立物品到用户的倒排表，对于每个物品都保存对该物品产生过行为的用户列表。\n",
    "\n",
    "令稀疏矩阵 $C[u][v] = |N(u) \\cap N(v)|$ ，假设用户 $u$ 和用户 $v$ 同时属于倒排表中 $K$ 个物品对应的用户列表，则 $C[u][v]=K$ 。可以扫描倒排表中每个物品对应的用户列表，将用户列表中的两两用户对应的 $C[u][v]$ **加1** 。最终得到所有用户之间不为0的 $C[u][v]$ 。\n",
    "\n",
    "相应的伪码：\n",
    "\n",
    "```python\n",
    "def user_similarity(train):\n",
    "    import math\n",
    "\n",
    "    # build inverse table for item_users\n",
    "    item_users = dict()\n",
    "    for u, items in train.items():\n",
    "        for i in items.keys():\n",
    "            if i not in item_users:\n",
    "                item_users[i] = set()\n",
    "            item_users[i].add(u)\n",
    "\n",
    "    # calculate co-related items between users\n",
    "    C = dict()\n",
    "    N = dict()\n",
    "    for i, users in item_users.items():\n",
    "        for u in users:\n",
    "            N[u] += 1\n",
    "            for v in users:\n",
    "                if u == v:\n",
    "                    continue\n",
    "                C[u][v] += 1\n",
    "\n",
    "    # calculate final similarity matrix W\n",
    "    W = dict()\n",
    "    for u, related_users in C.items():\n",
    "        for u, cuv in related_users.items():\n",
    "            W[u][v] = cuv / math.sqrt(N[u] * N[v])\n",
    "    return W\n",
    "```\n",
    "\n",
    "下面是使用 **NumPy** 实现的代码示例：\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def cos_sim(x, y):\n",
    "    \"\"\"余弦相似性\n",
    "\n",
    "    Args:\n",
    "    - x: mat, 以行向量的形式存储\n",
    "    - y: mat, 以行向量的形式存储\n",
    "\n",
    "    :return: x 和 y 之间的余弦相似度\n",
    "    \"\"\"\n",
    "    numerator = x * y.T  # x 和 y 之间的内积\n",
    "    denominator = np.sqrt(x * x.T) * np.sqrt(y * y.T)\n",
    "    return (numerator / denominator)[0, 0]\n",
    "```\n",
    "\n",
    "对于任意矩阵，计算任意两个行向量之间的相似度：\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def similarity(data):\n",
    "    \"\"\"计算矩阵中任意两行之间的相似度\n",
    "    Args:\n",
    "    - data: mat, 任意矩阵\n",
    "\n",
    "    :return: w, mat, 任意两行之间的相似度\n",
    "    \"\"\"\n",
    "\n",
    "    m = np.shape(data)[0]  # 用户的数量\n",
    "    # 初始化相似矩阵\n",
    "    w = np.mat(np.zeros((m, m)))\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(i, m):\n",
    "            if not j == i:\n",
    "                # 计算任意两行之间的相似度\n",
    "                w[i, j] = cos_sim(data[i], data[j])\n",
    "                w[j, i] = w[i, j]\n",
    "            else:\n",
    "                w[i, j] = 0\n",
    "    return w\n",
    "```\n",
    "\n",
    "相似度矩阵 $w$ 是一个对称矩阵，而且在相似度矩阵中，约定自身的相似度的值为 $0$ 。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org6114739\"></a>\n",
    "### 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户\n",
    "\n",
    "得到用户之间的兴趣相似度后， **UserCF** 算法会给用户推荐和他兴趣最相似的 $K$ 个用户喜欢的物品。\n",
    "\n",
    "下面的公式度量了 **UserCF** 算法中用户 $u$ 对物品 $i$ 的感兴趣程度：\n",
    "\n",
    "\\begin{equation}\n",
    "p(u,i) = \\sum_{v \\in S(u,K) \\cap N(i)} w_{uv}r_{vi} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "其中， $S(u,K)$ 包含和用户 $u$ 兴趣最接近的 $K$ 个用户， $N(i)$ 是对物品 $i$ 有过行为的用户集合， $w_{uv}$ 是用户 $u$ 和用户 $v$ 的兴趣相似度， $r_{vi}$ 代表用户 $v$ 对物品 $i$ 的兴趣。因为使用的是单一行为的隐反馈数据，所以所有的 $r_{vi}=1$ 。\n",
    "\n",
    "下面的伪码实现了上面的 **UserCF** 算法：\n",
    "\n",
    "```python\n",
    "def recommend(user, train, W, K):\n",
    "    rank = dict()\n",
    "    interacted_items = train[user]\n",
    "    for v, wuv in sorted(W[u].items, key=itemgetter(1), reverse=True)[0:K]:\n",
    "        for i, rvi in train[v].items:\n",
    "            if i in interacted_items:\n",
    "                # we should filter items user interacted before\n",
    "                continue\n",
    "            rank[i] += wuv * rvi\n",
    "    return rank\n",
    "```\n",
    "\n",
    "下面是基于 NumPy 的代码实现：\n",
    "\n",
    "```python\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "def user_based_recommend(data, w, user):\n",
    "    \"\"\"基于用户相似性为用户 user 推荐物品\n",
    "\n",
    "    Args:\n",
    "    - data: mat, 用户物品矩阵\n",
    "    - w: mat, 用户之间的相似度\n",
    "    - user: int, 用户编号\n",
    "\n",
    "    :return: predict, list, 推荐列表\n",
    "    \"\"\"\n",
    "    m, n = np.shape(data)\n",
    "    interaction = data[user, ]  # 用户 user 与物品信息\n",
    "\n",
    "    # 找到用户 user 没有互动过的物品\n",
    "    not_inter = []\n",
    "    for i in range(n):\n",
    "        if interaction[0, i] == 0:  # 没有互动的物品\n",
    "            not_inter.append(i)\n",
    "\n",
    "    # 对没有互动过的物品进行预测\n",
    "    predict = {}\n",
    "    for x in not_inter:\n",
    "        item = np.copy(data[:, x])  # 找到所有用户对商品 x 的互动信息\n",
    "        for i in range(m):  # 对每一个用户\n",
    "            if item[i, 0] != 0:\n",
    "                if x not in predict:\n",
    "                    predict[x] = w[user, i] * item[i, 0]\n",
    "                else:\n",
    "                    predict[x] = predict[x] + w[user, i] + item[i, 0]\n",
    "    return sorted(predict.items(), key=lambda d: d[1], reverse=True)\n",
    "```\n",
    "\n",
    "在函数<code>user_based_recommend</code>中，主要分为3步：\n",
    "\n",
    "1.  找到用户<code>user</code>未互动的商品，存放到<code>not_inter</code>中\n",
    "2.  利用上面公式对没有互动过的物品进行打分，在打分过程中，首先对用户<code>user</code>未互动过的每一个物品，找到对其互动过的用户，再利用打分公式对该物品打分\n",
    "3.  将打分的最终结果按照降序排序并返回\n",
    "\n",
    "如果是 **TOP N** 推荐，为用户推荐前 $N$ 个打分最高的物品：\n",
    "\n",
    "```python\n",
    "def top_k(predict, n):\n",
    "    \"\"\"为用户推荐前 n 个物品\n",
    "\n",
    "    Args:\n",
    "    - predict: list, 排好序的物品列表\n",
    "    - k: int, 推荐的物品个数\n",
    "\n",
    "    :return: top_recom, list, top n 个物品\n",
    "    \"\"\"\n",
    "    top_recom = []\n",
    "    len_result = len(predict)\n",
    "    if n >= len_result:\n",
    "        top_recom = predict\n",
    "    else:\n",
    "        for i in range(n):\n",
    "            top_recom.append(predict[i])\n",
    "    return top_recom\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "通过对不同 $K$ 值下的测量发现：\n",
    "\n",
    "* 准确率和召回率并不和 $K$ 成线性关系，通过多次测量可以选择合适的 $K$ 值\n",
    "* $K$ 越大，推荐的结果越热门，流行度增大\n",
    "* $K$ 越大，推荐结果的覆盖率越低"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org2c0c7fc\"></a>\n",
    "\n",
    "## 用户相似度的改进 **User-IIF** 算法\n",
    "\n",
    "两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。\n",
    "\n",
    "John S. Breese在论文<sup><a id=\"fnr.4\" class=\"footref\" href=\"#fn.4\">4</a></sup>中提出的根据用户行为计算用户的兴趣相似度：\n",
    "\n",
    "\\begin{equation}\n",
    "w_{uv} = \\frac{\\sum_{i \\in N (u) \\cap N (v)} \\frac{1}{\\log{(1 + | N (i) |)}}}{\\sqrt{| N(u) | | N(v) |}} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "该公式通过 $\\frac{1}{\\log{(1 + | N (i) |)}}$ 惩罚了用户 $u$ 和用户 $v$ 共同兴趣列表中热门物品对他们相似度的影响。\n",
    "\n",
    "```python\n",
    "def user_similarity(train):\n",
    "    import math\n",
    "\n",
    "    # build inverse table for item_users\n",
    "    item_users = dict()\n",
    "    for u, items in train.items():\n",
    "        for i in items.keys():\n",
    "            if i not in item_users:\n",
    "                item_users[i] = set()\n",
    "            item_users[i].add(u)\n",
    "\n",
    "    # calculated co-rated items between users\n",
    "    C = dict()\n",
    "    N = dict()\n",
    "    for i, users in item_users.items():\n",
    "        for u in users:\n",
    "            N[u] += 1\n",
    "            for v in users:\n",
    "                if u == v:\n",
    "                    continue\n",
    "                C[u][v] += 1 / math.log(1 + len(users))\n",
    "\n",
    "    # calculate final similarity matrix W\n",
    "    W = dict()\n",
    "    for u, related_users in C.items():\n",
    "        for v, cuv in related_users.items():\n",
    "            W[u][v] = cuv / math.sqrt(N[u] * N[v])\n",
    "    return W\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "<a id=\"org452cecf\"></a>\n",
    "\n",
    "## 缺点\n",
    "\n",
    "-   随着网站用户数的增大，计算用户兴趣相似度矩阵越发困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。\n",
    "\n",
    "-   很难对推荐结果作出解释。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ein.tags": "worksheet-0",
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## 脚注\n",
    "\n",
    "<sup><a id=\"fn.1\" class=\"footnum\" href=\"#fnr.1\">1</a></sup> 中文常翻译为“杰卡德公式”，公式如下：\n",
    "\n",
    "\\begin{equation}\n",
    "J(A,B) = \\frac{|A \\cap B|}{| A \\cup B|} = \\frac{| A \\cap B|}{|A| + |B| - |A \\cap B|} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "<sup><a id=\"fn.2\" class=\"footnum\" href=\"#fnr.2\">2</a></sup> 假定 $A$ 和 $B$ 是两个 $n$ 维向量， $A$ 是 $[A_1, A_2, \\ldots, A_n]$ ， $B$ 是 $[B_1, B_2, \\ldots, B_n]$ ，则 $A$ 与 $B$ 的夹角 $\\theta$ 的余弦等于：\n",
    "\n",
    "\\begin{eqnarray}\n",
    "\\cos \\theta & = & \\frac{\\Sigma^n_{i = 1} (A_i \\times B_i)}\n",
    "{\\sqrt{\\Sigma^n_{i = 1} (A_i)^2} \\times \\sqrt{\\Sigma^n_{i = 1}\n",
    "(B_i)^2}} \\nonumber\\\\\n",
    "& = & \\frac{A \\cdot B}{| A | \\times | B |} \\nonumber\n",
    "\\end{eqnarray}\n",
    "\n",
    "这里的 $A_i$ 和 $B_i$ 分別代表向量 $A$ 和 $B$ 的各分量。\n",
    "\n",
    "<sup><a id=\"fn.3\" class=\"footnum\" href=\"#fnr.3\">3</a></sup> 这里使用 **Ochiai** 系数，或 **Ochiai-Barkman** 系数：\n",
    "\n",
    "\\begin{equation}\n",
    "K = \\frac{n(A \\cap B)}{\\sqrt{n(A) \\times n(B)}} \\nonumber\n",
    "\\end{equation}\n",
    "\n",
    "这里 $A$ 和 $B$ 是集合， $n(A)$ 是 $A$ 的元素个数。如果集合由位向量所代表，那么可看到Ochiai系数跟余弦相似性是等同的。\n",
    "\n",
    "<sup><a id=\"fn.4\" class=\"footnum\" href=\"#fnr.4\">4</a></sup> 参见John S. Breese、David Heckerman和Carl Kadie的论文“Empirical Analysis of Predictive Algorithms for Collaborative Filtering” (Morgan Kaufmann Publishers，1998)。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "name": "python3"
  },
  "name": "5-user-based-collaborative-filtering.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
